/**
 * @file   Tree.cpp
 * @author xingyifan
 * @date   2021/08/19 14:37:54
 * 
 * @brief  functions
 * 
 * 
 */

#include "Binary_Tree.h"

//初始化静态本地变量
Bnode *Binary_Tree::nil = NULL;
u_int Binary_Tree::count = 0;

/**
 * @file   Tree.cpp
 * @author xingyifan
 * @date   2021/08/19 22:17:08
 * 
 * @brief  binary tree's functions
 * 
 * 
 */

Bnode *Binary_Tree::get(int depth, int i) const
{
    //i从0开始，depth表示第几层
    Bnode *p = root;
    //获取全局位置
    double left = 0;
    double right = 1 << (depth - 1);
    int floor = 1;
    while (floor != depth && p != nil)
    {
        if (i < (left + right) / 2)
        {
            p = p->lc;
            right = (left + right) / 2;
        }
        else
        {
            p = p->rc;
            left = (left + right) / 2;
        }
        floor++;
    }
    return p;
}

int Binary_Tree::indexOf(T value)
{
    if (root == nil)
    {
        return NONE;
    }
    Bnode *p = root;
    int index = p->lc->size;
    while (p != nil)
    {
        if (p->value < value)
        {
            p = p->rc;
            index += p->lc->size + 1;
        }
        else if (p->value > value)
        {
            p = p->lc;
            index -= p->rc->size + 1;
        }
        else
        {
            return index;
        }
    }
    return NONE;
}

void Binary_Tree::insert(T value)
{
    size++;
    if (root == nil)
    {
        root = new Bnode;
        root->value = value;
        root->parent = nil;
        root->lc = nil;
        root->rc = nil;
        root->size = 1;
        return;
    }
    Bnode *p = root;
    Bnode *pos = nil; //插入位置
    while (true)
    {
        p->size++;
        if (p->value <= value)
        {
            if (p->rc != nil)
            {
                p = p->rc;
            }
            else
            {
                p->rc = new Bnode;
                pos = p->rc;
                break;
            }
        }
        else
        {
            if (p->lc != nil)
            {
                p = p->lc;
            }
            else
            {
                p->lc = new Bnode;
                pos = p->lc;
                break;
            }
        }
    }
    //赋值
    pos->value = value;
    pos->parent = p;
    pos->rc = nil;
    pos->lc = nil;
    pos->size = 1;
}

void Binary_Tree::remove(T value)
{
    Bnode *p = find_node(value);
    if (p == nil)
    {
        return;
    }
    Bnode *lp = p->lc;
    Bnode *rp = p->rc;
    //size调整
    change_size(root, p);
    if (rp == nil)
    {
        //用lp替换p
        replace(p, lp);
        //p大小不变，要减去1
        lp->size = p->size - 1;
        delete p;
    }
    else if (lp == nil)
    {
        //用rp替换p
        replace(p, rp);
        //p大小不变，要减去1
        rp->size = p->size - 1;
        delete p;
    }
    else
    {
        //if has rp, choose the min of rp as the new node
        Bnode *pos = min(rp);
        //size调整
        change_size(p, pos);

        //if new node is not rp, link the new's parent and new's rc
        if (pos != rp)
        {
            replace(pos, pos->rc);
            pos->rc = rp;
            rp->parent = pos;
        }
        //link the new and p's parent and p's lc, rc
        pos->lc = lp;
        lp->parent = pos;

        replace(p, pos);
        pos->size = p->size;
        delete p;
    }
}

// "└,├,┌,└,┐,┘,├,┤,┬,┴,┼,—,│"
void Binary_Tree::perfect_draw() const
{
    int h = get_h();
    //每行前面的空格数 2^n - 2 个
    for (int i = 0; i < h; i++)
    {
        int c = 1 << i;
        int blank = (1 << (h - i)) - 2;
        while (c > 0)
        {
            print_blank(blank);
            cout << i;
            //相邻间距 2^(n+1) - 1
            blank = (1 << (h - i + 1)) - 1;
            c--;
        }
        cout << endl;
        if (h == i + 1)
        {
            break;
        }
        c = 1 << (i + 1);
        blank = (1 << (h - i - 1)) - 2;
        print_blank(blank);
        while (c > 0)
        {
            if (c % 2 == 0)
            {
                cout << "|";
            }
            else
            {
                cout << "|";
            }
            blank = (1 << (h - i)) - 1;
            if (c > 1)
            {
                print_(blank);
            }
            c--;
        }
        cout << endl;
    }
}

void Binary_Tree::draw() const
{
    int h = get_h();
    //打印第一行
    int blank = (1 << h) - 2;
    print_blank(blank);
    cout << root->value << endl;

    //每行前面的空格数 2^n - 2 个
    //从第二行开始
    for (int i = 1; i < h; i++)
    {
        const int num = 1 << i;
        int c = num;
        Bnode **record = new Bnode *[num];
        blank = (1 << (h - i)) - 2;
        //前置空格
        print_blank(blank);

        //输出树枝行
        while (c > 0)
        {
            record[num - c] = get(i + 1, num - c);
            blank = (1 << (h - i)) - 1;
            //提前记录此行元素
            Bnode *p = record[num - c];
            if (p != nil)
            {
                //左端点
                if (c % 2 == 0)
                {
                    cout << "|";
                    print_(blank + 1);
                }
                else
                {
                    //回退一格，覆盖左端点为nil时产生的空格
                    cout << "\b-";
                    print_(blank);
                    cout << "|";
                    print_blank(2 * blank + 1);
                }
            }
            else if (c > 1)
            {
                //左端点
                if (c % 2 == 0)
                {
                    print_blank(blank + 2);
                }
                else
                {
                    print_blank(3 * blank + 2);
                }
            }
            c--;
        }
        cout << endl;

        c = num;
        blank = (1 << (h - i)) - 2;
        int d = 0;
        //输出元素行
        while (c > 0)
        {
            print_blank(blank);
            print_b(d);
            /*
            * 只需要在这里插入节点输出
            *
            */
            if (record[num - c] != nil)
            {
                //将可能的浮点型直接转为整型，便于格式化
                int int_value = record[num - c]->value;
                cout << int_value;
                d = digit(int_value) - 1;
            }
            else
            {
                cout << " ";
                d = 0;
            }
            //相邻间距 2^(n+1) - 1
            blank = (1 << (h - i + 1)) - 1;
            c--;
        }
        delete[] record;
        cout << endl;
    }
}

/**
 * @file   Tree.cpp
 * @author xingyifan
 * @date   2021/08/19 15:35:42
 * 
 * @brief  private functions
 * 
 * 
 */

void Binary_Tree::inorder_walk(ostream &out, Bnode *node) const
{
    if (node != nil)
    {
        inorder_walk(out, node->lc);
        out << node->value << " ";
        inorder_walk(out, node->rc);
    }
}

Bnode *Binary_Tree::successor(Bnode *p)
{
    //if has right, return the min of right
    if (p->rc != nil)
    {
        return min(p->rc);
    }
    //if no right, find parent until pos==nil or pos comes from left
    Bnode *pos = p->parent;
    while (pos != nil && pos->lc != p)
    {
        p = pos;
        pos = p->parent;
    }
    return pos;
}

Bnode *Binary_Tree::predeccessor(Bnode *p)
{
    //if has left, return the max of left
    if (p->lc != nil)
    {
        return max(p->lc);
    }
    //if no left, find parent until pos==nil or pos comes from right
    Bnode *pos = p->parent;
    while (pos != nil && pos->rc != p)
    {
        p = pos;
        pos = p->parent;
    }
    return pos;
}

Bnode *Binary_Tree::max(Bnode *p)
{
    if (p == nil)
    {
        return nil;
    }
    while (p->rc != nil)
    {
        p = p->rc;
    }
    return p;
}

Bnode *Binary_Tree::min(Bnode *p)
{
    if (p == nil)
    {
        return nil;
    }
    while (p->lc != nil)
    {
        p = p->lc;
    }
    return p;
}

Bnode *Binary_Tree::find_node(T value)
{
    Bnode *p = root;
    while (p != nil)
    {
        if (p->value < value)
        {
            p = p->rc;
        }
        else if (p->value > value)
        {
            p = p->lc;
        }
        else
        {
            break;
        }
    }
    return p;
}

void Binary_Tree::change_size(Bnode *head, Bnode *tail)
{
    while (tail != head)
    {
        tail = tail->parent;
        tail->size--;
    }
}

void Binary_Tree::replace(Bnode *u, Bnode *v)
{
    if (u == root)
    {
        root = v;
    }
    else if (u == u->parent->lc)
    {
        u->parent->lc = v;
    }
    else
    {
        u->parent->rc = v;
    }
    v->parent = u->parent;
}

int Binary_Tree::height(Bnode *node) const
{
    if (node != nil)
    {
        return MAX(height(node->lc), height(node->rc)) + 1;
    }
    return 0;
}

void Binary_Tree::clean(Bnode *node)
{
    if (node != nil)
    {
        clean(node->lc);
        clean(node->rc);
        delete node;
        node = nil;
    }
}